//
// Created by Administrator on 2022/10/17.
//
//拥有前序指针和后续指针的双向链表
#include <malloc.h>
#include <stdio.h>
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef int Status;

typedef struct DuLNode {
    ElemType data;
    struct DuLNode* prior;
    struct DuLNode* next;
} DuLNode ;
typedef struct DuLNode* DuLinkedList;
//创建一个双向链表，并插入i个数据
DuLinkedList CreateDuLL(DuLinkedList *list,int i){
    *list = (DuLinkedList)malloc(sizeof(DuLNode));
    DuLinkedList p =*list;
    p->prior=p;
    p->next=p;
    DuLinkedList q;
    for (int j = 0; j < i; ++j) {
        q= (DuLinkedList)malloc(sizeof(DuLNode));
        q->data= j;
        q->prior = p;
        p->next=q;
        p=p->next;
    }
    p->next = NULL;
    //返回尾节点
    return p;
}
void showNextDuLinkedList(DuLinkedList list){
    DuLinkedList p=list->next;
    while(p){
        printf("%d\n",p->data);
        p=p->next;
    }
}
int LengthList(DuLinkedList list){
    DuLinkedList p =list->next;
    int length = 0;
    while(p){
        p=p->next;
        length++;
    }
    return length;
}
void showPriorDuLinkedList(DuLinkedList list,DuLinkedList rear){
    while(rear!=list){
        printf("%d\n",rear->data);
        rear=rear->prior;
    }
}

Status insertList(DuLinkedList *list,int i,ElemType e){
    DuLinkedList p =*list;
    if(i<0|| i> LengthList(*list)+1){
        return ERROR;
    }
    //找到待插入位置的前一个节点
    for (int j = 0; j < i-1; ++j) {
        p=p->next;
    }
    //此时p为插入位置的上一个节点
    if(p){
        DuLinkedList q = (DuLinkedList) malloc(sizeof(DuLNode));
        q->data=e;
        q->next = p->next;
        p->next->prior = q;
        p->next=q;
        q->prior = p;
        return OK;
    }
    return ERROR;
}
Status deleteList(DuLinkedList *list,int i,ElemType *e){
    DuLinkedList p =*list;
    DuLinkedList q;
    if(i<0|| i> LengthList(*list)){
        return ERROR;
    }
    //找到待删除位置的前一个节点
    for (int j = 0; j < i-1; ++j) {
        p=p->next;
    }
    //此时p为删除位置的上一个节点
    if(p){

        q = p->next;//待删除节点
        *e=q->data;
        p->next =q->next;
        q->next->prior=p;
        free(q);
        return OK;
    }
    return ERROR;
}

void main(){
    DuLinkedList list;
    DuLinkedList rear = CreateDuLL(&list,5);
    printf("1:\n");
    showNextDuLinkedList(list);


    printf("2:\n");
    insertList(&list,5,999);
    showNextDuLinkedList(list);

    printf("3:\n");
    int data;
    deleteList(&list,2,&data);
    showNextDuLinkedList(list);
    printf("data:%d",data);

}